//
//  main.cpp
//  10.13-1
//
//  Created by 刘晨 on 2018/11/3.
//  Copyright © 2018 刘晨. All rights reserved.
//

#include <iostream>
using namespace std;
#define MAX_SIZE 100
typedef struct  Node{
    int child;
    Node * next;
}Node;
typedef struct Box{
    char data;
    int parent;
    Node *childHead;
}Box;

class Tree{
private:
    Box *box;
    int length;
    int size;
public:
    Tree(int size);
    void create();
    void addChild(char parent,char child);
    int locateChild(char child);
    int degree(char node);
};
Tree::Tree(int size){
    box = new Box[size];
    this->size = MAX_SIZE;
    length =size;
}
int  Tree::locateChild(char child){
    for (int i = 0; i<this->length; i++) {
        if(child == this->box[i].data) return i;
    }
    return -1;
}

void Tree::addChild(char parent, char child){
    int parentAddress = locateChild(parent);
    this->box[length++].data = child;
    Node *temp = new Node;
    temp->child = length-1;
    temp->next = this->box[parentAddress].childHead;
    this->box[parentAddress].childHead = temp;
    
//    temp->next=box[parentAddress].childHead->next;
//    box[parentAddress].childHead->next = temp;
}

void Tree::create(){
    char parentNode,childNode;
    int parentAdd,childAdd;
    Node *temp=NULL;
    cout<<"input Tree data\n";
    for (int i = 0; i<length; i++) {
        cin>>box[i].data;
        box[i].childHead=NULL;
    }
    
    cout<<"input data done\n"<<"start link parent and child\n";
    for (int j =0; j<length; j++) {
        cout<<"input parent node\n";
        cin>>parentNode;
        parentAdd = locateChild(parentNode);
        cout<<"input child node\n";
        cin>>childNode;
        while(childNode != '.'){
            temp = new Node;
            childAdd = locateChild(childNode);
            temp->child = childAdd;
//            temp->next = box[parentAdd].childHead->next;
//            box[parentAdd].childHead->next = temp;
            temp->next = box[parentAdd].childHead;
            box[parentAdd].childHead = temp; //没有带头结点的头插法
            cin>>childNode;
            
            
            //    temp->next=box[parentAddress].childHead->next;
            //    box[parentAddress].childHead->next = temp;
        }
        
    }
}
int Tree::degree(char node){
    Node *p = NULL;
    for (int i = 0; i<length; i++) {
        if( node == box[i].data ){
            p = box[i].childHead;
            break;
        }
    }
    int count = 0;
    while (p != NULL) {
        p=p->next;
        count++;
    }
    return count;
}

int main(){
    
    Tree a(9);
    a.create();
    cout<<a.degree('a')<<endl;
    a.addChild('a', 'w');
    cout<<a.degree('a')<<endl;
    return 0;
}
